论文 | 基于平均与块投影的随机Kaczmarz算法

近日，中国人民大学分布式人工智能实验室2023级博士生张泽义与沈栋教授合作的论文“Randomized Kaczmarz Algorithm with Averaging and Block Projection”被中国人民大学核心期刊BIT Numerical Mathematics接收。

研究背景

在系统控制、机器学习、信号处理、图像处理等领域中，许多问题或其某个环节可以归结为求解以下线性方程组系统

求解该系统的方法分为直接法(LU分解，Cholesky分解等)和间接法(Jacobi迭代，Gauss-Seidel迭代，Richardson迭代，successive overrelaxation迭代等)。后者又称迭代法，由于计算效率高而被广泛使用。Kaczmarz算法是迭代方法的一种，于1937年由Stefan Kaczmarz提出，是第一个探究超平面上的正交投影序列的数值方法。具体地，在每次迭代中，以某种规则（随机地或确定地）选择矩阵A的第i行和向量b的第i个分量，更新律为

其仅仅涉及原线性系统的某一行(即一个方程)，计算十分简单，体现了一种化繁为简，分而治之的思想，因而内存要求低、易扩展、易并行。以一个简单例子展示Kaczmarz算法的收敛过程：设平面上两个方程决定了两条直线，它们的交点为解x*，则迭代点x0, x1, ⋯, 有如下过程

其中x1是x0到直线A1 x=b1的正交投影，x2是x1到直线A2 x=b2的正交投影。通过依次交替投影，可以看到随着k增加，迭代点渐进地趋于解。

在计算机不是很发达的年代，Kaczmarz算法——也被熟知为代数重建技术(Algebraic Reconstruction Technique)——被应用到CT(computer tomography)重建的研究中，并于1972年在第一台医疗扫描仪中实施。随着硬件和软件的发展，涌现出大量高效的、能力更强的迭代方法。

随着数据规模的爆炸式增长，问题规模越来越大，随机化的方法成为一种主要的处理手段。尤以随机梯度下降(SGD)的应用最为广泛，随机化Kaczmarz方法恰是SGD的一个特例。在新世纪以来越来越多的学者对Kaczmarz算法进行了相关研究。

搜索“Kaczmarz“结果. 数据来源：Web of Science

我们认为随机化Kaczmarz方法有三个环节：选取行的方式，选取概率的分布，更新律。在更新律的诸多设计中，两类方法十分常见：一是行块的投影，二是平均化方法，相关文献综述请见文章引言。前者可以有效提高迭代收敛速率，后者易于并行且免于矩阵逆的计算。二者的结合可以有效平衡收敛速率和计算量。本文将两者结合起来进行统一分析，提供了一个框架式的算法averaging randomized block Kaczmarz(aRBK)算法，并给出了收敛性分析，为线性系统的算法设计提供新的思路。

主要工作

算法描述：

由原系统产生τ个子系统， 

子系统的每一行来自原系统。在每个子系统上执行随机化块投影算法(随机化块Kaczmarz算法)，然后将这许多子系统的结果进行加权平均，得到实际的迭代更新。

收敛结果：

对相容的线性系统，得到均方误差的线性收敛： 

可以看到对步长α的要求很简单。将此扩展到不相容的线性系统，也有线性收敛速度 

数值实验结果如下

算法加速：

文章从子系统的秩、更新距离和残差出发，设计了三种自适应的权重，在每次迭代自动地重新分配子系统的重要性，对那些“贡献”较大的子系统增加其权重，取得加速效果。

1）秩自适应的权重

2）更新距离自适应的权重 

3）残差自适应的权重 

在数值实验中，不同权重的效果如下，三种自适应权重都有加速迭代收敛的作用。

结论展望

文章还对步长、权重、子系统的重叠、子系统个数等算法设定条件进行了讨论和实验，形成了一个比较完整的算法框架，得到全局线性收敛结果，为线性系统的算法设计提供了启发。

迭代方法不仅可以求解数值问题，也能为控制算法的设计提供指导和理论分析技术，而且已经有一些基于线性方程求解的控制设计实践[1]-[6]. 前文提到，aRBK算法涉及三个环节，可以对应到控制问题中的数据获取规律，所获数据的重要性（资源）分配，控制输入的更新律；因此aRBK算法能为控制中的一些问题提供解决思路。优化方法已经十分广泛地应用到控制系统的设计中，相信迭代方法也能在控制问题中进一步开发，提供高效率的计算和优秀的控制效果。

第一作者

期刊介绍

BIT于1961年创办，最早广泛涵盖了计算机科学和技术领域；自 1992 年以来，重点一直放在数值数学上。BIT在快速发展的数值分析领域发表原创研究论文。BIT涵盖的基本领域是数值方法的开发和分析，以及科学计算算法的设计和使用。BIT重视的主题包括数值逼近、线性代数以及确定性和随机类型的常微分方程和偏微分方程。

文章信息

引用信息：

Zhang, Z., Shen, D. Randomized Kaczmarz algorithm with averaging and block projection. Bit Numer Math, vol. 64, Article number: 1, 2024.

文章链接：

https://link.springer.com/article/10.1007/s10543-023-01002-9

参考文献：

[1] Zhang, Z., Jiang, H., Shen, D., & Saab, S.S. (2023). Data-driven learning control algorithms for unachievable tracking problems. IEEE/CAA Journal of Automatica Sinica.

[2] Wu, Y., Meng, D., Wang, J., & Cai, K. (2023). Observer-Based Distributed Methods for Learning Control Systems. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 53, 2983-2994.

[3] Meng, D. (2023). Feedback of Control on Mathematics: Bettering Iterative Methods by Observer System Design. IEEE Transactions on Automatic Control, 68, 2498-2505.

[4] Wu, Y., & Meng, D. (2023). Data-based trackability criteria and control design for disturbed learning systems. Autom., 155, 111113.

[5] Meng, D., & Wu, Y. (2021). Control Design for Iterative Methods in Solving Linear Algebraic Equations. IEEE Transactions on Automatic Control, 67, 5039-5054.

[6] Zhang, Z., Jiang, H., Zeng, K., & Shen, D. (2023). Collaborative Learning Tracking for Networked Systems with Fading Communication. 2023 IEEE 12th Data Driven Control and Learning Systems Conference (DDCLS), 728-732.